/*
 * ListenableDijkstra.java
 *
 * Created on September 10, 2007, 5:31 PM
 *
 * Copyright 2008 David D. Emory
 * 
 * This file is part of Five Points. See <http://www.fpdev.org> for
 * additional information regarding the project.
 * 
 * Five Points is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * Five Points is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with Five Points.  If not, see <http://www.gnu.org/licenses/>.
 */
package org.fpdev.core.algo;

import java.util.*;

import org.jgrapht.*;
import org.jgrapht.event.TraversalListener;
import org.jgrapht.traverse.*;

/**
 * An implementation of <a
 * href="http://mathworld.wolfram.com/DijkstrasAlgorithm.html">Dijkstra's
 * shortest path algorithm</a> using <code>ClosestFirstIterator</code>.
 *
 * @author John V. Sichi
 * @since Sep 2, 2003
 */
public final class ListenableDijkstra<V, E> {
  //~ Instance fields --------------------------------------------------------
  private List<E> edgeList;
  private double pathLength;

  //~ Constructors -----------------------------------------------------------
  /**
   * Creates and executes a new DijkstraShortestPath algorithm instance. An
   * instance is only good for a single search; after construction, it can be
   * accessed to retrieve information about the path found.
   *
   * @param graph the graph to be searched
   * @param startVertex the vertex at which the path should start
   * @param endVertex the vertex at which the path should end
   */
  public ListenableDijkstra(Graph<V, E> graph,
          V startVertex,
          V endVertex,
          TraversalListener listener) {
    this(graph, startVertex, endVertex, listener, Double.POSITIVE_INFINITY);
  }

  /**
   * Creates and executes a new DijkstraShortestPath algorithm instance. An
   * instance is only good for a single search; after construction, it can be
   * accessed to retrieve information about the path found.
   *
   * @param graph the graph to be searched
   * @param startVertex the vertex at which the path should start
   * @param endVertex the vertex at which the path should end
   * @param radius limit on path length, or Double.POSITIVE_INFINITY for
   * unbounded search
   */
  public ListenableDijkstra(
          Graph<V, E> graph,
          V startVertex,
          V endVertex,
          TraversalListener listener,
          double radius) {
    if (!graph.containsVertex(endVertex)) {
      throw new IllegalArgumentException(
              "graph must contain the end vertex");
    }

    ClosestFirstIterator<V, E> iter =
            new ClosestFirstIterator<V, E>(graph, startVertex, radius);

    iter.addTraversalListener(listener);
    while (iter.hasNext()) {
      V vertex = iter.next();

      if (vertex.equals(endVertex)) {
        createEdgeList(graph, iter, endVertex);
        pathLength = iter.getShortestPathLength(endVertex);

        return;
      }
    }

    edgeList = null;
    pathLength = Double.POSITIVE_INFINITY;
  }

  //~ Methods ----------------------------------------------------------------
  /**
   * Return the edges making up the path found.
   *
   * @return List of Edges, or null if no path exists
   */
  public List<E> getPathEdgeList() {
    return edgeList;
  }

  /**
   * Return the length of the path found.
   *
   * @return path length, or Double.POSITIVE_INFINITY if no path exists
   */
  public double getPathLength() {
    return pathLength;
  }

  private void createEdgeList(
          Graph<V, E> graph,
          ClosestFirstIterator<V, E> iter,
          V endVertex) {
    edgeList = new ArrayList<E>();

    while (true) {
      E edge = iter.getSpanningTreeEdge(endVertex);

      if (edge == null) {
        break;
      }

      edgeList.add(edge);
      endVertex = Graphs.getOppositeVertex(graph, edge, endVertex);
    }

    Collections.reverse(edgeList);
  }
}

// End DijkstraShortestPath.java
